Допустимость алгоритма эвристического перебора
	Важным является вопрос, может ли алгоритм эвристического перебора с оценочной функций общего вида (т.е. выбираемой произвольно) гарантировать нахождение решающего пути за конечное число шагов в тех случаях, когда решение существует (как алгоритм поиска вширь). Понятно, что такой уверенности нет прежде всего для задач с бесконечными пространствами состояний. Вообще же, нередка ситуация, когда эвристика, сильно сокращающая перебор для большинства начальных состояний, в то же время для других начальных конфигураций либо не может уменьшить необходимую переборную работу (и решение задачи может искаться даже дольше, чем с использованием слепого метода), либо вовсе не может обеспечить обнаружение решающего пути.
	Математическое исследование алгоритма эвристического поиска – условий, гарантирующих нахождение им решения – было проведено для эвристических оценочных функций специального вида.
Разновидность алгоритма эвристического поиска, применяемого для поиска оптимального решающего пути и использующего при этом оценочную функцию некоторого специального вида, известен в литературе как А-алгоритм. Были доказаны важные свойства этого алгоритма, прежде всего, утверждение о его  допустимости.
Алгоритм перебора называют допустимым (или состоятельным), если для произвольного графа он всегда заканчивает свою работу построением оптимального пути к цели, при условии, что такой путь существует.
Пусть h*(V) – стоимость оптимального пути из произвольной вершины V в целевую вершину. 	Верна следующая теорема о допустимости А-алгоритма:
А-алгоритм, использующий некоторую эвристическую функцию вида (*), где 
g(V) – стоимость пути от начальной вершины до вершины V в дереве перебора, а
h(V) – эвристическая оценка оптимального пути из вершины V в целевую вершину,
является допустимым, если 	h(V)  h*(V)    для всех вершин V пространства состояний. 
А-алгоритм эвристического поиска, применяющий функцию h(V), удовлетворяющую этому условию, получил название А*-алгоритма.
	Практическое значение этой теоремы в том, что для допустимости А-алгоритма достаточно найти какую-либо нижнюю грань функции h*(V) и использовать ее в качестве h(V) – тогда оптимальность найденного алгоритмом решения будет гарантирована.
Если взять тривиальную нижнюю грань, т.е. установить h(V) = 0 для всех вершин пространства состояний, то допустимость будет обеспечена. Однако этот случай соответствует полному отсутствию какой-нибудь эвристической информации о задаче, и оценочная функция Est не имеет никакой эвристической силы, т.е. не сокращает возникающий перебор. А*-алгоритм ведет себя при этом аналогично поиску вширь. 
Точнее, при 	Est(V) = g(V) (где g(V) – стоимость пути от начальной вершины до вершины V ), мы получаем алгоритм, известный как алгоритм равных цен (или Алгоритм Дейкстры). Алгоритм равных цен представляет собой более общий вариант метода перебора в ширину, при котором вершины раскрываются в порядке возрастания стоимости g(V) , т.е. в первую очередь раскрывается вершина из списка нераскрытых вершин, для которой величина g имеет наименьшее значение.
	Если же, кроме того, положить стоимость с(VA, VB) = 0 для всех дуг пространства состояний, то А*-алгоритм просто превращается в неэффективный слепой поиск вширь.
Обе предложенные для игры в восемь эвристические функции Est1(V) и Est2(V) удовлетворяют условию допустимости А*-алгоритма. Первое их слагаемое d(V) есть стоимость пути к вершине V при стоимости всех дуг с(VA, VB) = 1. Функции отличаются лишь вторым слагаемым, и можно показать, что значение второй функции  всегда (т.е. для всех состояний), больше значения первой функции:	Est1(V)   Est2(V)  , что равнозначно  k (V)  s (V)  .
Действительно, во второй функции вклад каждой фишки в общую оценку-сумму s(V)  либо равен 0 (фишка стоит уже на «своем» месте), либо не меньше 1 (в противном случае), в первой же функции этот вклад в k(V) соответственно либо равен 0, либо  равен 1. 
Из последнего неравенства следует, что условие допустимости достаточно доказать только для второй функции Est2. Справедливость нужного условия  
s(V)  h*(V) следует из следующего соображения. Если бы фишки не мешали друг другу и могли двигаться до «своего» места по кратчайшему пути, как если бы других фишек на квадрате не было, то сумма длин таких путей для всех фишек была бы в точности равна значению s(V) . На самом же деле фишки редко когда могут двигаться по кратчайшей траектории из-за того, что на ней расположены другие фишки, поэтому длина (стоимость) оптимального решения h*(V) будет не меньше s(V).
	Заметим, что s(V) не учитывает должным образом трудность обмена местами двух соседних фишек, а поэтому ее эвристическая сила в принципе может быть повышена. В ряде случаев эвристическая сила некоторой оценочной функции может быть повышена просто путем умножения на положительную константу, большую единицы, однако часто такое повышение осуществимо только за счет отказа от допустимости алгоритма. Например, если для игры в восемь в качестве второй составляющей эвристической функции взять h(V) = 2s(V), то в ряде случаев такая функция будет убыстрять поиск и позволит решать более трудные задачи, но условие допустимости перестанет выполняться (так как для начального состояния на рис.15:  h*(V)  2s(V) ).
	Вообще в случае, когда верно неравенство h1(V)  h2(V) для всех вершин пространства состояний, не являющихся целевыми, А*-алгоритм, использующий эвристическую составляющую h2(V), называется более информированным, чем А*-алгоритм с функцией h1(V). Показано, что если эти функции статичны (т.е. не изменяются в процессе поиска), то более информированный алгоритм раскрывает всегда меньшее число вершин, прежде чем находит путь минимальной стоимости. Это значит, что более информированный алгоритм осуществляет более направленный, а значит, более эффективный (при прочих равных) поиск целевой вершины. Таким образом, понятие информированности отражает один из аспектов понятия эвристической силы оценочной функции при поиске в пространстве состояний.
	Итак, желательно подобрать такую эвристическую функцию h(V), которая была бы нижней границей h*(V) (чтобы гарантировать допустимость алгоритма) и была бы как можно ближе к h*(V) (чтобы обеспечить эффективность поиска). К сожалению, существуют задачи, для которых нельзя найти оценочную функцию, обеспечивающую во всех случаях как эффективность, так и допустимость эвристического поиска. Поэтому часто приходится останавливаться на эвристических функциях, сокращающих поиск во многих случаях ценой отказа от гарантии найти оптимальный решающий путь.
Заметим, что в идеальном случае, когда известна оценка h*(V), и она используется в качестве h(V), А*-алгоритм находит оптимальный решающий путь сразу, без раскрытия ненужных вершин.
Поиск на игровых деревьях
Деревья игры. Поиск выигрышной стратегии
Будем рассматривать класс игр двух лиц с полной информацией. В таких играх участвуют два игрока, которые поочередно делают свои ходы. В любой момент игры каждому игроку известно все, что произошло в игре к этому моменту и что может быть сделано в настоящий момент. Игра заканчивается либо выигрышем одного игрока (и проигрышем другого), либо ничьей. 
Таким образом, в рассматриваемый класс не попадают игры, исход которых зависит хотя бы частично от случая  большинство карточных игр, игральные кости, «морской бой» и проч. Тем не менее класс достаточно широк: в него входят такие игры, как шахматы, шашки, реверси, калах, крестики-нолики и другие игры. 
Для формализации и изучения игровых стратегий в классе игр с полной информацией может быть использован подход, основанный на редукции задач. При этом подходе должны быть определены следующие составляющие: форма описания задач и подзадач; операторы, сводящие задачи к подзадачам; элементарные задачи; а также задано описание исходной задачи.
Наиболее интересна задача поиска выигрышной стратегии для одного из игроков, отправляясь от некоторой конкретной конфигурации (позиции) игры (не обязательно начальной). При использовании подхода, основанного на редукции задач, выигрышная стратегия ищется  в процессе доказательства того, что игра может быть выиграна. Аналогично, поиск ничейной стратегии, исходя из некоторой конкретной позиции, ведется в процессе доказательства  того, что игра может быть сведена к ничьей.
Ясно, что описание решаемой задачи должно содержать описание конфигурации игры, для которой ищется нужная стратегия. Например, в шашках игровая позиция включает задание  положений на доске всех шашек, в том числе дамок. Обычно описание конфигурации содержит также указание, кому принадлежит следующий ход.
Пусть именами игроков будут ПЛЮС и МИНУС. Будем использовать следующие обозначения:
XS или YS  некоторая конфигурация игры, причем индекс S принимает значения  + или , указывая тем самым, кому принадлежит следующий ход (т.е. в конфигурации X+ следующий ход должен делать игрок ПЛЮС, а в X – игрок МИНУС);
W(XS)  задача доказательства того, что игрок ПЛЮС может выиграть, исходя из позиции XS;
V(XS)  задача доказательства того, что игрок МИНУС может выиграть, отправляясь от позиции XS.
Рассмотрим сначала игровую задачу W(XS). Операторы сведения  (редукции) этой задачи к подзадачам определяются исходя из ходов, допустимых в проводимой игре:
	Если в некоторой конфигурации X+ очередной ход делает игрок ПЛЮС, и имеется N допустимых ходов, приводящих соответственно к конфигурациям X1, X2, . . . XN , то для решения задачи W(X+) необходимо решить по крайней мере одну из подзадач W(Xi). Действительно, так как ход выбирает игрок ПЛЮС, то он выиграет игру, если хотя бы один из ходов ведет к выигрышу  см. рис. 2(а).
	 Если же в некоторой конфигурации Y ход должен сделать игрок МИНУС, и имеется K допустимых ходов, приводящих к конфигурациям Y1+ , Y2+ , . . . YK+, то для решения задачи W(Y) требуется решить каждую из возникающих подзадач W(Yi+). Действительно, поскольку ход выбирает МИНУС, то ПЛЮС выиграет игру, если выигрыш гарантирован ему после любого хода противника  см. рис. 2(б).

Последовательное применение данной схемы редукции к исходной конфигурации игры порождает И/ИЛИ-дерево (И/ИЛИ-граф), которое называют деревом (графом) игры. Дуги игрового дерева соответствуют ходам игроков, вершины  конфигурациям игры, причем листья дерева  это позиции, в которых игра завершается выигрышем, проигрышем или ничьей. Часть листьев являются заключительными вершинами, соответствующими элементарным задачам  позициям, выигрышным для игрока ПЛЮС. Заметим, что для конфигураций, где ход принадлежит ПЛЮСу, в игровом дереве получается ИЛИ-вершина, а для позиций, в которых ходит МИНУС, получается И-вершина.
Цель построения игрового дерева или графа  получение решающего поддерева для задачи W(XS), показывающего, как игрок ПЛЮС может выиграть игру из позиции XS независимо от ответов противника. Для этого могут быть применены разные алгоритмы поиска на И/ИЛИ-графах. Решающее дерево заканчивается на позициях, выигрышных для ПЛЮСа, и содержит полную стратегию достижения им выигрыша: для каждого возможного продолжения игры, выбранного противником, в дереве есть ответный ход, приводящий к победе.
Для задачи V(XS) схема сведения игровых задач к подзадачам аналогична: ходам игрока ПЛЮС будут соответствовать И-вершины, а ходам МИНУСа  ИЛИ-вершины, заключительные же вершины будут соответствовать позициям, выигрышным для игрока МИНУС.
Конечно, подобная редукция задач применима и в случае, когда нужно доказать существование ничейной стратегии в игре. При этом определение  элементарной задачи должно быть соответствующим образом изменено.
Рассмотрим в качестве иллюстрации простую игру, называемую «последний проигрывает». Два игрока поочередно берут по одной или две монеты из кучки, первоначально содержащей семь монет. Игрок, забирающий последнюю монету, проигрывает. 
На рис.3 показан полный граф игры для задачи V(7+), жирными дугами на нем выделен решающий И/ИЛИ-граф, который доказывает, что второй игрок (т.е. игрок МИНУС, начинающий вторым), всегда может выиграть. Конфигурация игры описана как число оставшихся в текущий момент монет, также указание, кому принадлежит следующий ход. Заключительные вершины, соответствующие элементарной задаче V(1+), т.е. выигрышу игрока МИНУС, в графе подчеркнуты. 
Представленная в решающем графе выигрышная стратегия может быть сформулирована словесно так: если в очередном ходе игрок ПЛЮС берет одну монету, то в следующем ходе МИНУС должен взять две, а если ПЛЮС берет две монеты, то МИНУС должен забрать одну. Отметим, что для аналогичной задачи W(7+) решающий граф построить не удастся (начальная вершина неразрешима); таким образом, у игрока ПЛЮС нет выигрышной стратегии в этой игре.

В большинстве игр, представляющих интерес, таких как шашки и шахматы, построить полные решающие деревья и найти полные игровые стратегии не представляется возможным. Например, для шашек число вершин в полном игровом дереве оценивается величиной порядка 1040, и просмотреть такое дерево практически нереально. Алгоритмы же упорядоченного перебора с применением эвристик не настолько уменьшают просматриваемую часть дерева игры, чтобы дать существенное, на несколько порядков, сокращение времени поиска.
Тем не менее для неполных игр в шашки и шахматы (например, для эндшпилей), так же как и для всех несложных игр, таких как  «крестики-нолики» на фиксированном квадрате небольшого размера, можно успешно применять алгоритмы поиска на И/ИЛИ-графах, позволяющие обнаруживать выигрышные и ничейные игровые стратегии.
Рассмотрим, к примеру, игру «крестики-нолики» на квадрате 33. Игрок ПЛЮС ходит первым и ставит крестики, а МИНУС  нолики. Игра заканчивается, когда составлена либо строка, либо столбец, либо диагональ из крестиков (в этом случае выигрывает ПЛЮС) или ноликов (выигрывает МИНУС). Оценим размер полного дерева игры: начальная вершина имеет 9 дочерних вершин, каждая из которых в свою очередь  8 дочерних; каждая вершина глубины 2 имеет 7 дочерних и т.д. Таким образом, число концевых вершин в дереве игры равно 9!=362880, но многие пути в этом дереве обрываются раньше на заключительных вершинах. Значит, в этой игре возможен полный просмотр дерева и нахождение выигрышной стратегии. Однако ситуация изменится при существенном увеличении размеров квадрата или же в случае неограниченного поля игры.
В таких случаях, как и во всех сложных играх вместо нереальной задачи поиска полной игровой стратегии решается, как правило, более простая задача  поиск для заданной позиции игры достаточно хорошего первого хода. 

Минимаксная процедура
С целью поиска достаточно хорошего первого хода просматривается обычно часть игрового дерева, построенного от заданной конфигурации. Для этого применяется один из переборных алгоритмов (в глубину, в ширину или эвристический) и некоторое искусственное окончание перебора вершин в игровом дереве: например, ограничивается время перебора или же глубина поиска.
В построенном таким образом частичном дереве игры оцениваются вершины, и по полученным оценкам определяется наилучший ход от заданной игровой конфигурации. При этом для оценивания концевых вершин (листьев) полученного дерева используется так называемая статическая оценочная функция, а для оценивания остальных вершин – корневой (начальной) и промежуточных между корневой и концевыми вершинами – используется так называемый минимаксный принцип.
Статическая оценочная функция, будучи применена к некоторой вершине-конфигурации игры, дает числовое значение, оценивающее различные достоинства этой игровой позиции. Например, для шашек могут учитываться такие (статические) элементы конфигурации игры, как продвинутость и подвижность шашек, количество дамок, контроль ими центра и проч. По сути, статическая функция вычисляет эвристическую оценку шансов на выигрыш одного из игроков. Для определенности будем рассматривать задачу выигрыша игрока ПЛЮС и соответственно поиска достаточно хорошего его первого хода от заданной конфигурации.
Будем придерживаться общепринятого соглашения, по которому значение статической оценочной функции тем больше, чем больше преимуществ имеет игрок ПЛЮС (над игроком МИНУС) в оцениваемой позиции. Очень часто оценочная функция выбирается следующим образом:
•	статическая оценочная функция положительна в позициях, где  игрок ПЛЮС имеет преимущества;
•	статическая оценочная функция отрицательна в конфигурациях, где МИНУС имеет преимущества;
•	статическая оценочная функция близка к нулю в позициях, не дающих преимущества ни одному из игроков.
Например, для шашек в качестве простейшей статической функции может быть взят перевес в количестве шашек (и дамок) у игрока ПЛЮС. Для игры «крестики-нолики» на фиксированном квадрате возможна такая статическая оценочная функция:
   +		если P есть позиция выигрыша игрока ПЛЮС
E(P) =  	   		если P есть позиция выигрыша МИНУСа
  (NL+ +NC+ +ND+ )(NL +NC +ND) 	в остальных случаях
где 	+  очень большое положительное число;
  очень маленькое отрицательное число;
NL+, NC+, ND+   соответственно число строк, столбцов и диагоналей, «открытых» для игрока ПЛЮС (т.е. где он еще может поставить три выигрышных крестика подряд),
а   NL, NC, ND  аналогичные числа для игрока МИНУС. 
На рис.3 приведены две игровые позиции (на квадрате 44) и соответствующие значения статической оценочной функции.

Подчеркнем, что с помощью статической оценочной функции оцениваются только концевые вершины дерева игры, для оценок же промежуточных вершин, как и начальной вершины, используется минимаксный принцип, основанный на следующей простой идее. Если бы игроку ПЛЮС пришлось бы выбирать один из нескольких возможных ходов, то он выбрал бы наиболее сильный ход, т.е. ход, приводящий к позиции с наибольшей оценкой. Аналогично, если бы игроку МИНУС пришлось бы выбирать ход, то он выбрал бы ход, приводящий к позиции с наименьшей оценкой. 

Сформулируем теперь сам минимаксный принцип:
▪ ИЛИ-вершине дерева игры приписывается оценка, равная максимуму оценок ее дочерних вершин;
▪ И-вершине игрового дерева приписывается оценка, равная минимуму оценок ее дочерних вершин.
Минимаксный принцип положен в основу минимаксной процедуры, предназначенной для определения наилучшего (более точно, достаточно хорошего) хода игрока исходя из заданной конфигурации игры S при фиксированной глубине поиска N в игровом дереве. Предполагается, что игрок ПЛЮС ходит первым (т.е. начальная вершина есть ИЛИ-вершина). Основные этапы этой процедуры таковы:

1.	Дерево игры строится (просматривается) одним из известных алгоритмов перебора (как правило, алгоритмом поиска вглубь) от исходной позиции S до глубины N;
2.	Все концевые вершины полученного дерева, т.е. вершины, находящиеся на глубине N, оцениваются с помощью статической оценочной функции;
3.	В соответствии с минимаксным принципом вычисляются оценки всех остальных вершин: сначала вычисляются оценки вершин, родительских для концевых, затем родительских для этих родительских вершин и так далее; таким образом оценивание вершин происходит при движении снизу вверх по дереву поиска  до тех пор, пока не будут оценены вершины, дочерние для начальной вершины, т.е. для исходной конфигурации S;
4.	Среди вершин, дочерних к начальной, выбирается вершина с наибольшей оценкой: ход, который к ней ведет, и есть искомый наилучший ход в игровой конфигурации S.

На рис.5 показано применение минимаксной процедуры для дерева игры, построенного до глубины N=3. Концевые вершины не имеют имен, они обозначены своими оценками  значениями статической оценочной функции. Числовые индексы имен остальных вершин показывают порядок, в котором эти вершины строились алгоритмом перебора вглубь. Рядом с этими вершинами находятся их минимаксные оценки, полученные при движении в обратном (по отношению к построению дерева) направлении. Таким образом, наилучший ход – первый из двух возможных.
На рассматриваемом игровом дереве выделена ветвь (последовательность ходов игроков), представляющая так называемую минимаксно-оптимальную игру, при которой каждый из игроков всегда выбирает наилучший для себя ход. Заметим, что оценки всех вершин этой ветви дерева совпадают, и оценка начальной вершины равна оценке концевой вершины этой ветви.
В принципе статическую оценочную функцию можно было бы применить и к промежуточным вершинам, и на основе этих оценок осуществить выбор наилучшего первого хода, например, сразу выбрать ход, максимизирующий значение статической оценочной функции среди вершин, дочерних к исходной. Однако считается, что оценки, полученные с помощью минимаксной процедуры, есть более надежные меры относительного достоинства промежуточных вершин, чем оценки, полученные прямым применением статической оценочной функции. Действительно, минимаксные оценки основаны на просмотре игры вперед и учитывают разные особенности, которые могут возникнуть в последующем, в то время как простое применение оценочной функции учитывает лишь свойства позиции как таковой. Это отличие статических и минимаксных оценок существенно для «активных», динамичных позиций игры (например, в шашках и шахматах к ним относятся конфигурации, в которых возникает угроза взятия одной или нескольких фигур). В случае же так называемых «пассивных», спокойных позиций статическая оценка может мало отличаться от оценки по минимаксному принципу.

Плэнер-алгоритм, реализующий минимаксную процедуру
Рассмотрим сначала написанную на Плэнере функцию MIN_MAX, реализующую минимаксную процедуру. Аргументы этой функции: Instate  исходная позиция игры, для которой ищется наилучший ход; N    глубина поиска, т.е. количество ходов вперед. Вырабатываемое функцией значение  это дочерняя для Instate позиция, соответствующая искомому наилучшему ходу.
[define MIN_MAX (lambda (Instate N)
   [SELECT_MAX [MM_EVALP .Instate  0 T ]] )]
Функция  MIN_MAX использует две вспомогательные функции: SELECT_MAX и MM_EVALP. Первая функция, SELECT_MAX выбирает из своего единственного аргумента-списка, состоящего из позиций и их оценок, позицию с наибольшей оценкой:
[define SELECT_MAX (lambda (List)
  [prog (Elem Max_elem )
      [fin Max_elem .List]
   SM [cond([fin Elem List] [return [2 .Max_elem]])
           ([gt [1 .Elem] [1 .Max_elem]]
              [set Max_elem .Elem]) ]
     [go SM]  ] )]
Функция MM_EVALP с тремя аргументами является главной рекурсивной функцией, оценивающей вершины дерева игры по минимаксному принципу. На каждом шаге рекурсии она оценивает вершину-позицию Position, находящуюся на глубине Depth и имеющую тип Deptype: "ИЛИ" при  Deptype=Т  и  "И" при Deptype=(). Исходная позиция (корневая вершина дерева) имеет тип Т и находится на глубине 0. Значением функции MM_EVALP является либо вычисленная оценка вершины Position (при Depth>0) либо список дочерних для Position позиций с их числовыми оценками (при Depth=0). 
При работе MM_EVALP используются вспомогательные функции, определение которых зависит от конкретной игры: OPENING, вычисляющая для заданной позиции игры список дочерних вершин-позиций, и STAT_EST  статическая оценочная функция. 
[define MM_EVALP (lambda (Position Depth Deptype)
   [prog (D             %дочерняя позиция;
          (Movelist()) %список ходов-позиций);
          Pvalue Dvalue) %оценки текущей и дочерней 
                            позиций;
% 1:установка развилки, включающей все дочерние вершины текущей позиции(список () добавлен в развилку, чтобы "поймать" момент ее закрытия);
    [set D [among (<OPENING .Position> ())]]
% 2: если развилка закрыта - возврат функцией подсчитанной оценки;
    [cond ([empty .D]
            [return [cond ([eq .Depth 0] .Movelist)
                          (t .Pvalue) ]] )]
% 3: вычисление оценки очередной дочерней позиции: либо применение статической функции, либо рекурсивный спуск;
   [cond ([eq .Depth [- .N 1]] 
            [set Dvalue [STAT_EST .D]])
         (t [set Dvalue [MM_EVALP .D
                                [+ 1 .Depth]
                                [not .Deptype]]] )]
% 4:пересчет оценки текущей позиции по минимаксному принципу;
    [cond ([hasval Pvalue] [pset Pvalue
               [cond(.Deptype [max .Pvalue .Dvalue])
                    (t [min .Pvalue .Dvalue]) ]])
          (t [pset Pvalue .Dvalue]) ]
% 5: при необходимости пересчет для исходной позиции списка ходов(дочерних позиций) с их оценками;
  [cond([eq .Depth 0]
         [pset Movelist(!.Movelist (.Dvalue .D)) ])]
% 6: возврат к другой альтернативе развилки;
    [fail]  ])]

Эвристический перебор на Лиспе

Приведем текст лисповской функции HEURISTIC_SEARCH, реализующей эвристический перебор в пространстве состояний с использованием эвристической оценочной функции EST (зависящей от конкретной поисковой задачи). Вычисляемая для каждого состояния эвристическая оценка хранится как четвертый элемент списка-описания состояния, а третий элемент этого списка является глубиной состояния в дереве поиска. Заметим, что на шаге 3, выбирая из списка Open первый элемент-вершину, мы тем самым выбираем вершину с минимальной оценкой, поскольку список Open всегда упорядочен по неубыванию оценок вершин-состояний, хранящихся в нем (это обеспечивается вспомогательной функцией MERGE).
   (defun HEURISTIC_SEARCH(StartState)
(prog (Open  Closed  Current 
             Deslist ;список дочерних вершин;
             Reflist ;список указателей;
             Depth ;глубина текущей вершины;)
 ;Шаг 1:;   (setq Open (list (list 'S0  StartState  0
                                 (EST (list StartState 0)))))
 ;Шаг 2:; НS(cond((null Open) (return())))
 ;Шаг 3:;   (setq Current (car Open))
            (setq Open (cdr Open))
            (setq Closed (cons Current Closed))
            (setq Depth (caddr Current))
 ;Шаг 4:;   (cond((IS_GOAL Current)
                  (return (SOLUTION Current Reflist))))
 ;Шаг 5:;   (setq Deslist (OPENING Current))
 ; Исключение повторных вершин-состояний; 
            (setq Deslist (RETAIN_NEW Deslist))
            (cond((null Deslist) (go НS) ))
 ;Шаг 6:;   (setq Open (MERGE (SORT(ADD_DEPTH_EST(add1 Depth) Deslist))
                              Open))
            (setq Reflist(append(CONNECT Deslist Current)
                                 Reflist))
            (go HS) ))

Данная функция использует вспомогательные функции OPENING, SOLUTION, IS_GOAL, CONNECT, EST (которые зависят от конкретной поисковой задачи), а также три вспомогательные функции: RETAIN_NEW, ADD_DEPTH_EST и MERGE.
Вспомогательная функция RETAIN_NEW оставляет в списке дочерних состояний Dlist только те, которые не порождались ранее – тем самым исключается зацикливание при поиске в произвольном графе. Вспомогательная функция SORT упорядочивает (по неубыванию эвристической оценки) список дочерних вершин, к элементам которого добавлена информация о глубине в дереве поиска и об оценке. Определения этих двух функций мы не рассматриваем.
   	Функция ADD_DEPTH_EST устанавливает глубину дочерних вершин и вычисляет их эвристическую оценку:
   (defun ADD_DEPTH_EST (Dn Slist)
      (cond((null Slist) ())
          (t (cons(list (caar Slist) (cadar Slist) Dn
                     (EST(list (cadar Slist) Dn)) )
                  (ADD_DEPTH_EST Dn (cdr Slist)) ) )) )
Функция MERGE выполняет слияние двух упорядоченных (по неубыванию эвристической оценки) списков состояний в результирующий упорядоченный список:
   (defun MERGE (L1 L2)
      (cond((null L1) L2)
           ((null L2) L1)
           ((gt (car (cdddar L1)) (car (cdddar L2)))
                (cons(car L2) (MERGE L1 (cdr L2))))
           (t   (cons(car L1) (MERGE (cdr L1) L2))) ))

Игра в восемь (Лисп)
Граф-пространство состояний для головоломки-игры в восемь достаточно велик (в игре в пятнадцать фишек он на порядок больше), поэтому хотя в принципе применимы алгоритмы слепого поиска, предпочтителен все же эвристический поиск. Опишем нужные для HEURISTIC_SEARCH вспомогательные лисп-функции:  IS_GOAL, EST, OPENING, SOLUTION, CONNECT - для игры в восемь. Состояние задачи (конфигурация игры) представляется списком из следующих элементов: 
•	идентификатор состояния (используются атомы S1, S2, S3, … , генерируемые встроенной лисп-функцией gensym); 
•	собственно описание состояния – список из номеров фишек, записанных последовательно по рядам квадрата;
•	число-глубина состояния-вершины в дереве перебора;
•	числовая эвристическая  оценка состояния.
В описание состояния включается также – в качестве первого элемента списка – обозначение того оператора движения пустой клетки, который привел к данному состоянию. Этот элемент нужен, чтобы  исключить тривиальные повторы состояний при раскрытии вершин. Операторы будут обозначаться соответственно именами-атомами right, left, up, down; а "пустышка" (пустая клетка) – символом  #. Отметим, что эвристическая оценка используется только в алгоритме эвристического перебора, а глубина вершины –  в алгоритмах эвристического перебора и ограниченного перебора вглубь. 
Для примера, приведенного на рис. 5 в основной части текста  День 10, лекции № 19, № 20, начальное состояние S0 имеет такой вид: (? 2 8 3 1 6 4 7 # 5). Символ «?» означает, что оператора, который привел к данному состоянию, нет. При обращении к функции HEURISTIC_SEARCH с таким параметром на Шаге 1 в описание состояния S0 будут добавлены: этот идентификатор, информация о глубине (0) и эвристической оценке (4), затем будет сформирован список Open:
((S0 (? 2 8 3 1 6 4 7 # 5) 0 4))
Дочерние вершины S0:
(S1 ('right 2 8 3 1 6 4 7 5 #))
(S2 ('left  2 8 3 1 6 4 # 7 5))
(S3 ('up    2 8 3 1 # 4 7 6 5))
будут построены (именно в таком порядке) на Шаге 5 функцией OPENING. Список этих вершин станет значением переменной Deslist.
На шаге 6 в эти описания будет добавлена информация о глубине вершин (1) и их эвристических оценках (6, 6, 4) – в функции ADD_DEPTH_EST.
Описанные ниже лисп-функции для игры в восемь пригодны и для игры в пятнадцать, так как размер стороны игрового квадрата, равный 3, используется в них как глобальная переменная (переменная Size). Другая глобальная переменная (Goalstate), хранит описание целевого состояния (без идентификатора, глубины и  эвристической оценки). Значение оценочной функции EST –  сумма числа фишек, стоящих не на «своих» местах,  и длины пути  (глубины) оцениваемого состояния в дереве поиска.

     (defun IS_GOAL(State)
            (equal (cdadr State) Goalstate ))

     (defun EST (S)
        (prog(Len G  N  E1 E2)
            (setq Len (cadr S)) (setq N 0)
            (setq S (cdar S)) (setq G Goalstate)
     ;одновременный просмотр списков-описаний;
     ;     заданного и целевого состояний;
         ES (cond((null S) (return (+ (- N 1) Len)) ))
            (setq E1 (car S)) (setq S (cdr S))
            (setq E2 (car G)) (setq G (cdr G))
            (cond((neq E1 E2) (setq N (add1 N))
                 ((eq  E1 '#) (setq N (add1 N)))
            (go ES) ))

   (defun OPENING (State)
      (prog(Op St  Dlist K  I J El)
    ; выделение составных элементов описания состояния;
          (setq St (cadr State))
          (setq Op (car St))  (setq St (cdr St))
          (setq State St) (setq K 0)
    ; поиск порядкового номера К "пустышки" в списке;
       OP (setq El (car St))
          (setq K (add1 K))
          (cond ((neq El '#) (setq St(cdr St)) (go OP) ))
    ; вычисление номера ряда и номера столбца "пустышки";
          (setq I(add1(mod K Size))) (setq J (rem K Size))
    ; поочередно проверка возможности движения «пустышки»;
    ; вправо/влево/вверх/вниз; за счет анализа оператора Op;
    ; исключаем в дереве поиска тривиальные циклы;
    ; после применения двух операторов в исходное состояние;
          (cond((and (neq Op 'left) (< J Size))
                    (ADD_STATE 'right K (add1 K)) ))
          (cond((and (neq Op 'right) (> J 1))
                    (ADD_STATE 'left K (sub1 K)) ))
          (cond((and (neq Op 'down) (> I 1))
                    (ADD_STATE 'up K (- K Size)) ))
          (cond((and (neq Op 'up) (< I Size))
                    (ADD_STATE 'down K (+ K Size)) ))
          (return Dlist) ))

При раскрытии используется вспомогательная функция ADD_STATE, добавляющая в список дочерних вершин список-описание новой вершины из 2 элементов: идентификатора этой вершины (его генерирует функция gensym) и списка номеров фишек. В ADD_STATE применяется  встроенная лисп- функция NTH, выбирающая из заданного списка элемент с указанным порядковым номером.
   (defun  ADD_STATE (Op K1 K2)
    (push(list(gensym)
          (cons Op
           (cond((< K1 K2)
                 (EXCHANGE State 1 '# K1 (NTH K2 State)K2))
            (t (EXCHANGE State 1(NTH K2 State)K2 '# K1))) ))
          Dlist))

Рекурсивная функция EXCHANGE, используемая в ADD_STATE, формирует новое состояние игры путем перестановки заданных элементов исходного состояния-списка List (переменная K служит для просмотра  этого списка, при обращении к функции ее значение равно 1).
   (defun EXCHANGE (List K Elem1 K1 Elem2 K2)
     (cond((eql K K1) (cons Elem2
            (EXCHANGE(cdr List)(add1 K)Elem1 K1 Elem2 K2) ))
          ((eql K K2)(cons Elem1 (cdr List)) )) )

Функция CONNECT формирует список указателей от текущей вершины-состояния Curr  к заданным (в списке Dlist) дочерним вершинам-состояниям. Каждый указатель есть трехэлементный список из идентификатора родительской вершины, идентификатора дочерней вершины и названия связывающего их оператора.
   (defun CONNECT (Dlist Curr)
      (prog (D Di Ci Rlist)
        C (setq D (car Dlist)) (setq Dlist (cdr Dlist))
          (setq Di (car D))  (setq Ci (car Curr))
          (setq Rlist(cons (list Ci Di (caadr D))Rlist))
          (cond ((null Dlist) (return Rlist) ))
          (go C) ))
Функция SOLUTION, выделяя решающий путь, строит  последовательность (названий) операторов, преобразующих начальное состояние в целевое (ее аргумент Reflist – список всех указателей-связей между состояниями). Для поиска указателя к очередной вершине решающего пути функция использует  вспомогательную функцию LOOK_FOR . 
   (defun SOLUTION (Goal Reflist)
     (prog (Sollist ;список, в котором строится решение;
 Gi Edge)
         (setq Gi (car Goal))
       S (cond((eq Gi 'S0) (return Sollist) ))
         (setq Edge (LOOK_FOR Gi Reflist))
         (setq Sollist (cons(caddr Edge) Sollist))
         (setq Gi (car Edge))
         (go S) ))

   (defun LOOK_FOR (Id List)
         (cond((null List) (quote error))
              ((eq ID (cadar List)) (car List))
              (t(LOOK_FOR Id (cdr List)) )) )

В заключение приведем блок, инициализирующий эвристический поиск решения игры в восемь. В самом его начале устанавливаются значения параметров встроенной функции gensym.

   (prog(Goalstate Initstate Size)
         (setq *gensym-prefix* 'S)
         (setq *gensym-count* 1)
         (setq Size 3)
         (setq Goalstate '(1 2 3 8 # 4 7 6 5))
         (setq Initstate '(? 2 8 3 1 6 4 7 # 5))
         (HEURISTIC_SEARCH Initstate))